package com.sunny;

public class BinarySearch {

    public static void main(String[] args) {
        BinarySearch binarySearch = new BinarySearch();
        int[] arr = {1,2,3,3,3,3,4,5,5,6,7,8,8,8,8,8,8,8,8,8,9,10,10};
        System.out.println(binarySearch.findFirstGT(arr, 0, arr.length-1, 3));
        System.out.println(binarySearch.findFirstGE(arr, 0, arr.length-1, 5));
        System.out.println(binarySearch.findLastLE(arr, 0, arr.length-1, 11));
        System.out.println(binarySearch.findLastLT(arr, 0, arr.length-1, 4));

    }

    //找到第一个大于的值的下标
    public int findFirstGT(int[] arr, int s, int t, int val){
        while (s<t){
            int mid = (s+t)>>1;
            if(arr[mid] > val){
                t = mid;
            }else{
                s = mid + 1;
            }
        }
        return s;
    }

    //找到第一个大于等于的值的下标
    public int findFirstGE(int[] arr, int s, int t,int val){
        while (s<t){
            int mid = (s+t)>>1;
            if(arr[mid] >= val){
                t = mid;
            }else{
                s = mid + 1;
            }
        }
        return s;
    }

    public int findLastLE(int[] arr, int s, int t,int val){
        while (s<t){
            int mid = (s+t+1)>>1;
            if(arr[mid] <= val){
                s = mid;
            }else{
                t = mid - 1;
            }
        }
        return s;
    }

    public int findLastLT(int[] arr, int s, int t, int val){
        while (s<t){
            int mid = (s+t+1)>>1;
            if(arr[mid] < val){
                s = mid;
            }else{
                t = mid - 1;
            }
        }
        return s;
    }

}
